package class31;

import class10.Light3;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class BSTtoDoubleLinkedList {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node convert1(Node head) {
        Queue<Node> queue = new LinkedList<>();
        inOrderToQueue(head, queue);
        if (queue.isEmpty()) {
            return head;
        }
        head = queue.poll();
        Node pre = head;
        pre.left = null;
        Node cur = null;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = null;
        return head;
    }

    public static void inOrderToQueue(Node head, Queue<Node> queue) {
        if (head == null) {
            return;
        }
        inOrderToQueue(head.left, queue);
        queue.offer(head);
        inOrderToQueue(head.right, queue);
    }

    public static Node convert2(Node head) {
        if (head == null) {
            return null;
        }
        return process(head).start;
    }

    public static class Info {
        public Node start;
        public Node end;

        public Info(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }

    public static Info process(Node X) {
        if (X == null) {
            return new Info(null, null);
        }
        Info leftInfo = process(X.left);
        Info rightInfo = process(X.right);
        if (leftInfo.end != null) {
            leftInfo.end.right = X;
        }
        X.left = leftInfo.end;
        X.right = rightInfo.start;
        if (rightInfo.start != null) {
            rightInfo.start.left = X;
        }
        return new Info(
                leftInfo.start != null ? leftInfo.start : X,
                rightInfo.end != null ? rightInfo.end : X
        );
    }
}
